package Studing;

/**
 * @ClassName Sort
 * @Description: TODO
 * @Author hl
 * @Date 2020/7/28
 * @Version V1.0
 **/
public class Sort {
    public static void main(String[] args) {
        int []arr={7,5,6,2,1,3};

       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]);
       }
        System.out.println();
        heaepSort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]);
        }

    }

    public static void heaepSort(int []arr){
        //构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);
            adjustHeap(arr,0,j);
        }
    }
    public static void adjustHeap(int[]arr,int i,int length){
        int temp=arr[i];
        for(int k=2*i+1;k<length;k=k*2+1){
            if(k+1<length&&arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>temp){
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }

    public static void QuickSort(int []a,int low,int high){
        if(low>high){
            return;
        }
        int  i=low,j=high,key=a[low];
        while(i<j) {
            while (i < j && a[j] > key) {
                j--;
            }
            if(i<j){
                a[i++] = a[j];
            }

            while(i<j&&a[i] < key){
                i++;
            }
            if(i<j){
                a[j--]=a[i];
            }
        }
        a[i]=key;
        QuickSort(a,low,i-1);
        QuickSort(a,i+1,high);
    }


    public static void QuckSort3(int []arr,int l,int r){
       if(l>=r){
           return;
       }
       int random=(int)(Math.random()*(r-l+1)+l);
       swap(arr,l,random);
       int v=arr[l];
       int cl=l;
       int cr=r+1;
       int i=l+1;
       while(i<cr){
           if(arr[i]<v){
               swap(arr,cl+1,i);
               i++;
               cl++;
           }else{
               if(arr[i]>v){
                   swap(arr,cr-1,i);
                   cr--;
               }else{
                   i++;
               }
           }
       }
       swap(arr,l,cl);
        QuckSort3(arr,l,cl-1);
        QuckSort3(arr,cr,r);

    }
    public  static  void swap(int []arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
